var MiaIJ = function( i,j ) {
	this.i = i;
	this.j = j;
	this.toString = function() { return '{i:'+this.i+',j:'+this.j+'}' };
};

var MapM69 = function( table, tileSize ) {

	this.mapCoord = function( v ) {
		return Math.floor( v / this.getTileSize() );
	};

	this.clear = function( x, y ) {
		return this.clearIJ( this.mapCoord( y ), this.mapCoord( x ) );
	};

	this.clearIJ = function( i, j ) {
		return this.isInBounds( i, j ) ? this.isClearCell( this.cellAt( j, i ) ) : false;
	};

	this.isInBounds = function( i, j ) {
		return !( i < 0 || j < 0 || i >= this.getH() || j >= this.getW() );
	};

	// pathing

	this.astar = function( sx, sy, ex, ey ) {
		var map = this;

		var si = map.mapCoord( sy );
		var sj = map.mapCoord( sx );
		var ei = map.mapCoord( ey );
		var ej = map.mapCoord( ex );

		var w = map.getW();
		var h = map.getH();

		var start = new MiaIJ( si, sj );
		var goal  = new MiaIJ( ei, ej );

		var path = AStar.astar(
			  start
			, goal
			, AStar.heuristic_estimate_of_distance
			, function neighbor_nodes( a ) { return map.neighbors( a.i, a.j ); }
			, AStar.dist_between
			, AStar.equals
		);
		//Util.log( 'path=' + path );
		return path;
	};

	this.neighbors = function( i, j ) {
		var neighbors = [];
		var map = this;
		var clearPush = function( i, j ) {
			if ( map.isClearCell( map.cellAt( j, i ) ) ) neighbors.push( new MiaIJ( i, j ) );
		};
		clearPush( i - 1, j );
		clearPush( i + 1, j );
		clearPush( i, j - 1 ); 
		clearPush( i, j + 1 );
		return neighbors;
	};      

	this.startXY = function() {
		return {
			  x:(this.getStart().getX() * this.getTileSize() + this.getTablePosition().x)
			, y:(this.getStart().getY() * this.getTileSize() + this.getTablePosition().y)
		}
	};

	/* internals (mostly) */

	this.setTablePosition = function( tablePosition ) {
		this.tablePosition_ = tablePosition;
	};

	this.getTablePosition = function() {
		return this.tablePosition_;
	};

	this.setTileSize = function( tileSize ) {
		this.tileSize_ = tileSize;
	};

	this.getTileSize = function() {
		return this.tileSize_;
	};

	this.cellAt = function( x, y ) {
		return this.getCells()[ y ][ x ];
	};

	this.setCells = function( cells ) {
		this.cells_ = cells;
	};

	this.getCells = function() {
		return this.cells_;
	};

	this.setW = function( w ) {
		this.w_ = w;
	};

	this.getW = function() {
		return this.w_;
	};

	this.setH = function( h ) {
		this.h_ = h;
	};

	this.getH = function() {
		return this.h_;
	};

	this.fillCell = function( cell ) {
		cell.parentNode.setAttribute( 'wall', 'true' );
	};

	this.clearCell = function( cell ) {
		cell.parentNode.removeAttribute( 'wall' );
	};

	this.isClearCell = function( cell ) {
		return !this.isFullCell( cell );
	};

	this.isFullCell = function( cell ) {
		return 'true' == cell.parentNode.getAttribute( 'wall' );
	};

	this.fillBoard = function() {
		for ( var i = 0 ; i < this.getH() ; i++ ) {
			for ( var j = 0 ; j < this.getW() ; j++ ) {
				this.fillCell( this.getCells()[ i ][ j ] );
			}
		}
	};

	this.dig = function( x1,y1, x2,y2 ) {
		for ( var y = y1 ; y < y2 ; y++ ) {
			for ( var x = x1 ; x < x2 ; x++ ) {
				this.clearCell( this.getCells()[ y ][ x ] );
			}
		}
	};

	this.out = function( v, max ) {
		return v < 0 || v > max;
	};

	this.boned = function( x1,y1, x2,y2 ) {
		return ( false 
			|| this.out( x1, this.getW() ) 
			|| this.out( x2, this.getW() ) 
			|| this.out( y1, this.getH() ) 
			|| this.out( y2, this.getH() ) 
		);
	};

	this.split = function( x1,y1, x2,y2 ) {
		if ( this.boned( x1,y1, x2,y2 ) ) return;

		var w = x2 - x1;
		var h = y2 - y1;
		var a = w * h;

		if ( a < 16 + Math.random() * 64 ) { 
			this.dig( x1 + 1, y1 + 1, x2 - 1, y2 -1 );
		} else {
			if ( w < h ) { 
				var h2 = Math.floor( h / 2 );
				h2 = Math.floor( h2 - ( Math.random() * h2 * 0.8 ) );
				this.connect( 
					  x1, y1,        x2, y1 + h2 + 1
					, x1, y1 + h2,   x2, y2 
					, false
				);
			} else {
				var w2 = Math.floor( w / 2 );
				w2 = Math.floor( w2 - ( Math.random() * w2 * 0.8 ) );
				this.connect( 
					  x1, y1,        x1 + w2 + 1, y2
					, x1 + w2, y1,   x2, y2
					, true
				);
			}
		}
	};

	this.saucyOpening = function( x, y ) {
		var open = false;
		if ( x >=0 && y >=0 && x < this.getW() && y < this.getH() ) {
			open = this.isClearCell( this.getCells()[ y ][ x ] );
		}
		return open;
	};

	this.opening = function( x, y ) {
		return ( false 
			|| this.saucyOpening( x, y )
			|| this.saucyOpening( x+1, y )
			|| this.saucyOpening( x-1, y )
			|| this.saucyOpening( x, y+1 )
			|| this.saucyOpening( x, y-1 )
		);
	};

	this.connect = function( x1,y1, x2,y2, a1,b1, a2,b2, horizontal ) {
		if ( this.boned( x1,y1, x2,y2 ) ) return;
		if ( this.boned( a1,b1, a2,b2 ) ) return;
		this.split( x1,y1, x2,y2 );
		this.split( a1,b1, a2,b2 );
		if( horizontal ) {
			this.connectHorizontal( x1,y1, x2,y2, a1,b1, a2,b2 );
		} else {
			this.connectVertical( x1,y1, x2,y2, a1,b1, a2,b2 );
		}
	};

	this.connectHorizontal = function( x1,y1, x2,y2, a1,b1, a2,b2 ) {
		var ymid = Math.floor( y1 + ( y2 - y1 ) / 2 );
		var fy = -1;
		var left = -1;
		var right = -1;

		for ( var y = ymid ; y < y2 && ( -1 == left || -1 == right ) ; y++ ) {
			left = this.connectLeft( x1, x2 - 1, y );
			if ( -1 != left ) {
				right = this.connectRight( x2 + 1, a2, y );
			}
			if ( -1 != left && -1 !=right ) {
				fy = y;
			}
		}
		if ( -1 == left || -1 == right ) {
			left = right = -1;
		}
		for ( var y = ymid ; y >= y1 && ( -1 == left || -1 == right ); y-- ) {
			left = this.connectLeft( x1, x2 - 1, y );
			if ( -1 != left ) {
				right = this.connectRight( x2 + 1, a2, y );
			}
			if ( -1 != left && -1 !=right ) {
				fy = y;
			}
		}

		if ( -1 != left && -1 != right ) {
			for ( var x = left + 1 ; x < right ; x++ ){
				this.clearCell( this.getCells()[ fy ][ x ] );
			}
		}
	};

	this.connectVertical = function( x1,y1, x2,y2, a1,b1, a2,b2 ) {
		var xmid = Math.floor( x1 + ( x2 - x1 ) / 2 );
		var fx = -1;
		var up = -1;
		var down = -1;

		for ( var x = xmid ; x < x2 && ( -1 == up || -1 == down ) ; x++ ) {
			up = this.connectUp( y1, y2 - 1, x );
			if ( -1 != up ) {
				down = this.connectDown( y2 + 1, b2, x );
			}
			if ( -1 != up && -1 !=down ) {
				fx = x;
			}
		}

		if ( -1 == up || -1 == down ) {
			up = down = -1;
		}

		for ( var x = xmid ; x >= x1 && ( -1 == up || -1 == down ); x-- ) {
			up = this.connectUp( y1, y2 - 1, x );
			if ( -1 != up ) {
				down = this.connectDown( y2 + 1, b2, x );
			}
			if ( -1 != up && -1 !=down ) {
				fx = x;
			}
		}

		if ( -1 != up && -1 != down ) {
			for ( var y = up + 1 ; y < down ; y++ ){
				this.clearCell( this.getCells()[ y ][ fx ] );
			}
		}
	};

	this.connectLeft = function( x1, x2, y ) {
		var found = -1;
		for ( var x = x2 ; x > x1 && -1 == found ; x-- ) {
			if ( this.saucyOpening( x, y ) ) {
				found = x;
			}
		}
		return found;
	};

	this.connectRight = function( x2, a2, y ) {
		var found = -1;
		for ( var x = x2 ; x < a2 && -1 == found ; x++ ) {
			if ( this.saucyOpening( x, y ) ) {
				found = x;
			}
		}
		return found;
	};

	this.connectUp = function( y1, y2, x ) {
		var found = -1;
		for ( var y = y2 ; y > y1 && -1 == found ; y-- ) {
			if ( this.saucyOpening( x, y ) ) {
				found = y;
			}
		}
		return found;
	};

	this.connectDown = function( y2, b2, x ) {
		var found = -1;
		for ( var y = y2 ; y < b2 && -1 == found ; y++ ) {
			if ( this.saucyOpening( x, y ) ) {
				found = y;
			}
		}
		return found;
	};

	this.classify = function( cell, i, j, w, h ) {
		var type = 'empty';

		if ( this.isFullCell( cell ) ) {
			var left  = ( 0 != j )     ? this.isFullCell( this.getCells()[ i ][ j - 1 ] ) : false;
			var right = ( w - 1 != j ) ? this.isFullCell( this.getCells()[ i ][ j + 1 ] ) : false;
			var up    = ( 0 != i )     ? this.isFullCell( this.getCells()[ i - 1 ][ j ] ) : false;
			var down  = ( h - 1 != i ) ? this.isFullCell( this.getCells()[ i + 1 ][ j ] ) : false;
			var rd    = ( h - 1 != i && w - 1 != j ) ? this.isFullCell( this.getCells()[ i + 1 ][ j + 1 ]  ) : false;

			if ( false ) {
			}
			else if ( 0 == i && w - 1 == j ) {
				type = ( 'up_end' );
			}
			else if ( right && down && !rd ) {
				type = ( 'lup' );
			} 
			else if ( left && right && !down ) { 
				type = ( 'top' );
			} 
			else if ( up && down && !right ) {
				type = ( 'left' );
			} 
			else if ( left && !right && !up && !down ) {
				type = ( 'left_end' );
			} 
			else if ( up && !down && !left && !right ) { 
				type = ( 'down_end' );
			} 
			else if ( down && !up && !right ) { 
				type = ( 'up_end' );
			}
			else if ( !down && !left && right ) {
				type = ( 'right_end' );
			}
			//else if ( up && left && !down && !right ) {
				//type = ( 'bup' );
			//} 
			else if ( !down && !right ) {
				type = ( 'bup' ); // TODO: really need a "pillar" class
			} else {
				type = ( 'surround' )
			}
		} 
		return type;
	};

	this.fixClasses = function() {
		var w = this.getW();
		var h = this.getH();
		for ( var i = 0 ; i < h ; i++ ) {
			for ( var j = 0 ; j < w ; j++ ) {
				var cell = this.getCells()[ i ][ j ];
				var type = this.classify( cell, i, j, w, h );
				if ( type ) {
					Util.classy( cell.parentNode, type );
				}
			}
		}

		Util.classy(
			this.cellAt( this.getExit().getX(), this.getExit().getY() ).parentNode
			, 'stairs_d' 
		);
	};

	this.setStart = function( start ) {
		this.start_ = start;
	};

	this.getStart = function() {
		return this.start_;
	};

	this.setExit = function( exit ) {
		this.exit_ = exit;
	};

	this.getExit = function() {
		return this.exit_;
	};

	this.randomPoint = function() {
		return new Point2d( 
			Math.floor( Math.random() * this.getW() )
			, Math.floor( Math.random() * this.getH() )
		);
	};

	this.findFloor = function( p ) {
		return (
			this.isClearCell( this.cellAt( p.getX(), p.getY() ) )
			? p
			: this.findFloor_( p )
		);
	};

	this.findFloor_ = function( p ) {
		var w = this.getW();
		var h = this.getH();
		var max = w;
		if ( max > h ) {
			max = h;
		}
		var px = p.getX();
		var py = p.getY();
		var done = false;
		for ( var d = 0 ; d < max && !done ; d++ ) {

			for ( var x = px - d ; x < px + d + 1 && !done ; x++ ) {

				if ( x < 0 ) continue;
				if ( x >= w ) break;

				for ( var y = py - d ; y < py + d + 1 && !done ; y++ ) {
					if ( y < 0 ) continue;
					if ( y >= h ) break;

					if ( this.isClearCell( this.cellAt( x, y ) ) ) {
						p.setX( x );
						p.setY( y );
						done = true;
					}
				}
			}
		}
		return p;
	};

	this.randomFloor = function() { 
		var pt = this.randomPoint();
		while ( this.isFullCell( this.cellAt( pt.getX(), pt.getY() ) ) ) {
			pt = this.randomPoint();
		}
		return pt;
	};

	this.randomStart = function() {
		this.setStart( this.randomFloor() );
	};

	this.randomExit = function() {
		this.setExit( this.randomFloor() );
	};

	this.setPaused = function( paused ) {
		this.paused_ = paused;
	};

	this.getPaused = function() {
		return this.paused_;
	};

	this.pickStartAndExit = function() {
		//this.randomStart();
		//this.randomExit();

		var imax = this.getH() - 1;
		var jmax = this.getW() - 1;
		var si = 1;
		var sj = 1;
		var ei = imax;
		var ej = jmax;

		if ( 0.5 < Math.random() ) {
			if ( 0.5 < Math.random() ) { 
				ei = 1;
			} else {
				ej = 1;
			}
		}

		if ( 0.1 < Math.random() ) {
			si = Math.floor( imax / 2 );
		}
		if ( 0.1 < Math.random() ) {
			sj = Math.floor( jmax / 2 );
		}

		if ( 0.5 < Math.random() ) {
			var tmp;
			tmp = si;
			si = ei;
			ei = tmp;

			tmp = sj;
			sj = ej;
			ej = tmp;
		}
		this.setStart( this.findFloor( new Point2d( sj ,si ) ) );
		this.setExit(  this.findFloor( new Point2d( ej ,ei ) ) );
	};

	this.randomBoard = function() {
		this.fillBoard();
		this.split( 0, 0, this.getW(), this.getH() );

		this.pickStartAndExit();

		//this.cellAt( this.getStart().getX(), this.getStart().getY() ).innerHTML = '!!!';
		//this.cellAt( this.getExit().getX(), this.getExit().getY() ).innerHTML = '???';
		this.fixClasses();
	};

	this.init = function( table, tileSize ) {
		this.setTileSize( tileSize );
		this.setCells( [] );

		this.setTablePosition( Util.elementPosition( table ) );

		var thiz = this;
		Util.walkNode(
			table
			, function isDiv( n ) { return Util.isTag( 'DIV' ); }
			, function eachDiv( div ) {
				var i = div.getAttribute( 'i' );
				var j = div.getAttribute( 'j' );
				if ( !thiz.getCells()[ i ] ) {
					thiz.getCells()[ i ] = [];
				}
				thiz.getCells()[ i ][ j ] = div;
			}
		);
		this.setH( this.getCells().length );
		this.setW( this.getCells()[ 0 ].length );

		this.randomBoard();
	};

	this.init( table, tileSize );
};
